package graph

import (
	"traning/algorithm/union_set"
	"traning/algorithm/utility/heap"
)


/*
	并查集与堆的实现，需要参考对应章节。
*/
func KruskalMinSum(graph Graph) int {
	// 初始化结果权重
	var ans int

	// 获取所有的点，使用点创建并查集
	nodeArr := []interface{}{}
	for _, node := range graph.Nodes {
		nodeArr = append(nodeArr, node)
	}
	// 初始化并查集，用于判断两点是否连通
	nodeUnionSet := union_set.NewUnionSet(nodeArr)
	// 创建小根堆，使遍历的边有序
	smallHeap := heap.NewSmallHeap(len(graph.Edges))
	for edge, _ := range graph.Edges {
		smallHeap.Push(edge)
	}
	// 从小到大遍历所有的边
	for smallHeap.Size() > 0 {
		edge := smallHeap.Pop().(*Edge)
		if !nodeUnionSet.IsSameSet(edge.From, edge.To) {
			// 如果边两头的点不在同一个集合，选择该边，加上该边的权重
			ans += edge.Weight
			// 选择边后，需要将两个点连通
			nodeUnionSet.Union(edge.From, edge.To)
		}
	}
	return ans
}
